package eda.tests;

import java.util.Random;

import junit.framework.Assert;
import junit.framework.Test;
import junit.framework.TestCase;
import eda.hashTable.HashTableImpl;
import eda.util.ADTNoSuchElement;
import eda.util.ADTUnderflowException;
import eda.util.HashingUtil;


public class TestHashChaining extends TestCase implements Test{

	HashTableImpl<Integer, String> hashTable;
	HashingUtil<Integer, String> hashUtil;
	String tableToString30 = 
	"[ 0 = [], 1 = [], 2 = [], 3 = [], 4 = [], 5 = [], 6 = [], 7 = [], 8 = [], 9 = [], 10 = [], 11 = []," +
	" 12 = [], 13 = [], 14 = [], 15 = [], 16 = [], 17 = [], 18 = [], 19 = [], 20 = [], 21 = [], 22 = []," +
	" 23 = [], 24 = [], 25 = [], 26 = [], 27 = [], 28 = [], 29 = [] ]";
	String tableToString50 = 
	"[ 0 = [], 1 = [], 2 = [], 3 = [], 4 = [], 5 = [], 6 = [], 7 = [], 8 = [], 9 = [], 10 = [], 11 = []," +
	" 12 = [], 13 = [], 14 = [], 15 = [], 16 = [], 17 = [], 18 = [], 19 = [], 20 = [], 21 = [], 22 = []," +
	" 23 = [], 24 = [], 25 = [], 26 = [], 27 = [], 28 = [], 29 = [], 30 = [], 31 = [], 32 = [], 33 = []," +
	" 34 = [], 35 = [], 36 = [], 37 = [], 38 = [], 39 = [], 40 = [], 41 = [], 42 = [], 43 = [], 44 = []," +
	" 45 = [], 46 = [], 47 = [], 48 = [], 49 = [] ]";
	private String tableToString70 = 
    "[ 0 = [], 1 = [], 2 = [], 3 = [], 4 = [], 5 = [], 6 = [], 7 = [], 8 = [], 9 = [], 10 = [], 11 = []," +
	" 12 = [], 13 = [], 14 = [], 15 = [], 16 = [], 17 = [], 18 = [], 19 = [], 20 = [], 21 = [], 22 = []," +
	" 23 = [], 24 = [], 25 = [], 26 = [], 27 = [], 28 = [], 29 = [], 30 = [], 31 = [], 32 = [], 33 = []," +
	" 34 = [], 35 = [], 36 = [], 37 = [], 38 = [], 39 = [], 40 = [], 41 = [], 42 = [], 43 = [], 44 = []," +
	" 45 = [], 46 = [], 47 = [], 48 = [], 49 = [], 50 = [], 51 = [], 52 = [], 53 = [], 54 = [], 55 = []," +
	" 56 = [], 57 = [], 58 = [], 59 = [], 60 = [], 61 = [], 62 = [], 63 = [], 64 = [], 65 = [], 66 = []," +
	" 67 = [], 68 = [], 69 = [] ]";
	private String tableToString90 = 
    "[ 0 = [], 1 = [], 2 = [], 3 = [], 4 = [], 5 = [], 6 = [], 7 = [], 8 = [], 9 = [], 10 = [], 11 = []," +
	" 12 = [], 13 = [], 14 = [], 15 = [], 16 = [], 17 = [], 18 = [], 19 = [], 20 = [], 21 = [], 22 = []," +
	" 23 = [], 24 = [], 25 = [], 26 = [], 27 = [], 28 = [], 29 = [], 30 = [], 31 = [], 32 = [], 33 = []," +
	" 34 = [], 35 = [], 36 = [], 37 = [], 38 = [], 39 = [], 40 = [], 41 = [], 42 = [], 43 = [], 44 = []," +
	" 45 = [], 46 = [], 47 = [], 48 = [], 49 = [], 50 = [], 51 = [], 52 = [], 53 = [], 54 = [], 55 = []," +
	" 56 = [], 57 = [], 58 = [], 59 = [], 60 = [], 61 = [], 62 = [], 63 = [], 64 = [], 65 = [], 66 = []," +
	" 67 = [], 68 = [], 69 = [], 70 = [], 71 = [], 72 = [], 73 = [], 74 = [], 75 = [], 76 = [], 77 = []," +
	" 78 = [], 79 = [], 80 = [], 81 = [], 82 = [], 83 = [], 84 = [], 85 = [], 86 = [], 87 = [], 88 = []," +
	" 89 = [] ]";
	private String tableToString100 = 
    "[ 0 = [], 1 = [], 2 = [], 3 = [], 4 = [], 5 = [], 6 = [], 7 = [], 8 = [], 9 = [], 10 = [], 11 = []," +
	" 12 = [], 13 = [], 14 = [], 15 = [], 16 = [], 17 = [], 18 = [], 19 = [], 20 = [], 21 = [], 22 = []," +
	" 23 = [], 24 = [], 25 = [], 26 = [], 27 = [], 28 = [], 29 = [], 30 = [], 31 = [], 32 = [], 33 = []," +
	" 34 = [], 35 = [], 36 = [], 37 = [], 38 = [], 39 = [], 40 = [], 41 = [], 42 = [], 43 = [], 44 = []," +
	" 45 = [], 46 = [], 47 = [], 48 = [], 49 = [], 50 = [], 51 = [], 52 = [], 53 = [], 54 = [], 55 = []," +
	" 56 = [], 57 = [], 58 = [], 59 = [], 60 = [], 61 = [], 62 = [], 63 = [], 64 = [], 65 = [], 66 = []," +
	" 67 = [], 68 = [], 69 = [], 70 = [], 71 = [], 72 = [], 73 = [], 74 = [], 75 = [], 76 = [], 77 = []," +
	" 78 = [], 79 = [], 80 = [], 81 = [], 82 = [], 83 = [], 84 = [], 85 = [], 86 = [], 87 = [], 88 = []," +
	" 89 = [], 90 = [], 91 = [], 92 = [], 93 = [], 94 = [], 95 = [], 96 = [], 97 = [], 98 = [], 99 = [] ]"  ;
	
	protected void setUp() throws Exception{
		
		hashTable = new HashTableImpl<Integer, String>();
		hashUtil = new HashingUtil<Integer, String>();

	}
	
	public void testIsEmpty() throws Exception{
		
		Assert.assertTrue(hashTable.isEmpty());
		
		for (int i = 0; i < 30; i++) {
			hashTable.insert(i, Integer.toString(i));
		}
		
		Assert.assertFalse(hashTable.isEmpty());
		
		for (int i = 0; i < 30; i++) {
			hashTable.remove(i);
		}
		
		Assert.assertTrue(hashTable.isEmpty());
	}
	
	public void testFull() throws Exception{
		
		Assert.assertFalse(hashTable.full());
		
		for (int i = 0; i < 142; i++) {
			hashTable.insert(i, Integer.toString(i));
		}
		
		// Fills all the cells of the table with elements
		Assert.assertTrue(hashTable.full());
		
		for (int i = 0; i < 142; i++) {
			hashTable.remove(i);
		}
		
		Assert.assertFalse(hashTable.full());
	}
	
	public void testSize() throws Exception{
		
		Assert.assertEquals(0, hashTable.size());
		
		for (int i = 0; i < 142; i++) {
			hashTable.insert(i, Integer.toString(i));
			Assert.assertEquals(i + 1, hashTable.size());
		}
		
		Assert.assertTrue(hashTable.full());
		
		for (int i = 0; i < 142; i++) {
			hashTable.remove(i);
			Assert.assertEquals(141 - i, hashTable.size());
		}
		
		Assert.assertEquals(0, hashTable.size());
	}
	
	
	
	public void testInsert() throws Exception{
		
		Assert.assertTrue(hashTable.isEmpty());
		Assert.assertFalse(hashTable.full());
		Assert.assertEquals(hashTable.size(), 0);
		
		Assert.assertEquals(tableToString30,hashTable.toString());
		
		
		// Inserts elements until the moment before the size reaches 75% of the table length without rehashing
		for ( int i=0; i<22; i++ ){
			hashTable.insert(new Integer(i), String.valueOf(i));
			Assert.assertFalse(hashTable.isEmpty());
			Assert.assertFalse(hashTable.full());
			Assert.assertEquals(hashTable.size(), i + 1);
			Assert.assertEquals(String.valueOf(i) , hashTable.search(i));
			Assert.assertTrue(hashTable.containsKey(i));
			tableToString30 = hashUtil.chainingInsertElement(tableToString30, i, Integer.toString(i), 30);
			Assert.assertEquals(tableToString30, hashTable.toString());
		}
				
		// Inserts one more element, rehashing
		hashTable.insert(22, "22");
		
		for (int i = 0; i < 23; i++) {
			tableToString50 = hashUtil.chainingInsertElement(tableToString50, i, Integer.toString(i), 50);
		}
		Assert.assertEquals(tableToString50, hashTable.toString());
		
		
		
		// Inserts elements until the size gets in the eminence of rehashing
		for (int i = 23; i < 37; i++) {
			hashTable.insert(i, Integer.toString(i));
			tableToString50 = hashUtil.chainingInsertElement(tableToString50, i, Integer.toString(i), 50);
			Assert.assertEquals(tableToString50, hashTable.toString());
		}
		
		// Inserts one more element, rehashing
		hashTable.insert(37, Integer.toString(37));
		
		for (int i = 0; i < 38; i++) {
			tableToString70 = hashUtil.chainingInsertElement(tableToString70, i, Integer.toString(i), 70);
		}
		Assert.assertEquals(tableToString70 , hashTable.toString());	
		
		
		
		// Inserts elements until the size gets in the eminence of rehashing
		for (int i = 38; i < 52; i++) {
			hashTable.insert(i, Integer.toString(i));
			tableToString70 = hashUtil.chainingInsertElement(tableToString70, i, Integer.toString(i), 70);
			Assert.assertEquals(tableToString70, hashTable.toString());
		}
		
		// Inserts one more element, rehashing
		hashTable.insert(52, Integer.toString(52));
		
		for (int i = 0; i < 53; i++) {
			tableToString90 = hashUtil.chainingInsertElement(tableToString90 , i, Integer.toString(i), 90);
		}
		Assert.assertEquals(tableToString90 , hashTable.toString());
		
		
		
		// Inserts elements until the size gets in the eminence of rehashing
		for (int i = 53; i < 67; i++) {
			hashTable.insert(i, Integer.toString(i));
			tableToString90 = hashUtil.chainingInsertElement(tableToString90, i, Integer.toString(i), 90);
			Assert.assertEquals(tableToString90, hashTable.toString());
		}
		
		// Inserts one more element, rehashing
		hashTable.insert(67, Integer.toString(67));
		
		for (int i = 0; i < 68; i++) {
			tableToString100 = hashUtil.chainingInsertElement(tableToString100, i, Integer.toString(i), 100);
		}
		Assert.assertEquals(tableToString100 , hashTable.toString());
		
		// Inserts more than 100 elements (until the table gets full) and the table can not rehash anymore
		
		for (int i = 68; i < 142; i++) {
			hashTable.insert(i, Integer.toString(i));
			tableToString100 = hashUtil.chainingInsertElement(tableToString100, i, Integer.toString(i), 100);
			Assert.assertEquals(tableToString100, hashTable.toString());
		}
		
		Assert.assertFalse(hashTable.isEmpty());
		Assert.assertTrue(hashTable.full());
	}

	public void testRemove() throws Exception{
		
		Assert.assertTrue(hashTable.isEmpty());
		Assert.assertFalse(hashTable.full());
		Assert.assertEquals(hashTable.size(), 0);
		
		Assert.assertEquals(tableToString30,hashTable.toString());
		
		// Tries to remove an element when the table is empty
		try {
			hashTable.remove(0);
			Assert.fail("It should not have gotten here.");
		} catch (ADTUnderflowException e) {
			Assert.assertEquals("Structure is empty", e.getMessage());
		}
		
		// Inserts elements until the moment the size reaches 75% of the table length and it rehashes
		for ( int i=0; i<23; i++ ){
			hashTable.insert(i, Integer.toString(i));
			tableToString50 = hashUtil.chainingInsertElement(tableToString50, i, Integer.toString(i), 50);
		}
		
		Assert.assertEquals(tableToString50, hashTable.toString());

		// Tries to remove an element which is not in the table
		try {
			hashTable.remove(23);
			Assert.fail("It should not have gotten here.");
		} catch (ADTNoSuchElement e) {
			Assert.assertEquals("No such element is in the structure", e.getMessage());
		}

		// Removes (in decreasing order) the inserted elements from the table
		for ( int i=22; i>-1; i-- ){
			hashTable.remove(new Integer(i));
			if (i == 0){
				Assert.assertTrue(hashTable.isEmpty());
			}
			else{
				Assert.assertFalse(hashTable.isEmpty());
			}
			Assert.assertFalse(hashTable.full());
			Assert.assertEquals(hashTable.size(), i);
			Assert.assertNull("The search should have returned null.", hashTable.search(i));
			tableToString50 = hashUtil.chainingRemoveElement(tableToString50, i, Integer.toString(i), 50);
			Assert.assertEquals(tableToString50, hashTable.toString());	
		}
		
		// Tries to remove an element when the table is empty
		try {
			hashTable.remove(0);
			Assert.fail("It should not have gotten here.");
		} catch (ADTUnderflowException e) {
			Assert.assertEquals("Structure is empty", e.getMessage());
		}
	}
	
	public void testSearchAndContainsKey()throws Exception{
		
		
		int[] randomNumbers = new int[23];
		Random random = new Random();
		
		//insert and search elements with random keys
		for(int i = 0; i < randomNumbers.length; i++){
			randomNumbers[i] = (random.nextInt());
		}
		
		for(int i: randomNumbers){
			hashTable.insert(i, "RandomValue"+i);
		}
		
		for(int i: randomNumbers){
			Assert.assertTrue(hashTable.containsKey(i));
			Assert.assertEquals("RandomValue"+i, hashTable.search(i));
		}
		
		//insert and search element with biggest key
		hashTable.insert(new Integer(10000), "BiggestKey");
		Assert.assertTrue(hashTable.containsKey(new Integer(10000)));
		Assert.assertEquals("BiggestKey", hashTable.search(new Integer(10000)));
		
		//remove and try find
		hashTable.remove(new Integer(10000));
		Assert.assertFalse(hashTable.containsKey(new Integer(10000)));
		Assert.assertEquals(null, hashTable.search(new Integer(10000)));
		
		for(int i : randomNumbers){
			hashTable.remove(i);
			Assert.assertFalse(hashTable.containsKey(i));
			Assert.assertEquals(null, hashTable.search(i));		
		}		
	}
	
	protected void tearDown() throws Exception {
	}
}